/**
 * 递归遍历树形数据，查找到目标节点的路径
 *
 * @param id 寻找的节点id
 * @param forest 森林
 * @param path 路径结果
 * @param getIdMethod 获取id的方法
 * @param getChildrenListMethod 获取子级列表的方法
 */
function findPathFromForestDFS<S, T>(
  id: S,
  forest: T[] | undefined,
  path: T[],
  getIdMethod: (node: T) => S,
  getChildrenListMethod: (node: T) => T[] | undefined
): boolean {
  if (!forest) {
    return false
  }
  for (const node of forest) {
    path.push(node)

    // 找到目标节点 或者 下一层递归告诉我需要立即结束递归，则返回true（返回true表示立即结束整个递归）
    if (
      id === getIdMethod(node) ||
      findPathFromForestDFS(id, getChildrenListMethod(node), path, getIdMethod, getChildrenListMethod)
    ) {
      return true
    }
    path.pop()
  }
  return false
}

/**
 * 树通用深度优先遍历工具（注意，此方法无法不会遍历顶级节点，单独使用此方法意义不大，请调用TreeUtil.foreachDFS()）
 * @param tree 树
 * @param before 在递归之前调用，类似前序遍历。
 *    - node：为当前节点
 *    - level：为当前节点的层级（从1开始）
 *    - parentNode：为当前节点的上级节点（如果没有上级节点则为undefined）
 *    - 返回值：返回true表示继续递归，返回false表示立即停止整个递归
 *
 * @param after 在递归之后调用，类似后序遍历。
 *    - node：为当前节点
 *    - level：为当前节点的层级（从1开始）
 *    - parentNode：为当前节点的上级节点（如果没有上级节点则为undefined）
 *    - 返回值：返回true表示继续递归，返回false表示立即停止整个递归
 *
 * @param getChildrenListMethod 获取子节点列表的方式，默认使用children字段
 * @param level 当前递归的层级，从1开始，默认1
 * @return boolean
 *         对于递归过程来说：true继续递归，false停止整个递归
 *         对于调用者来说：true表示完成递归所有节点，false表示在before或after参数控制下递归提前终止
 * @author 郭泳辰
 */
function treeForeachDFS<NODE>(
  tree: NODE | undefined,
  before?: (node: NODE, level: number, parentNode?: NODE) => boolean,
  after?: (node: NODE, level: number, parentNode?: NODE) => boolean,
  getChildrenListMethod: (node: NODE) => NODE[] | undefined = getChildrenListMethodDefault,
  level: number = 1
): boolean {
  if (!tree) {
    return true
  }
  const childrenNodeList: NODE[] | undefined = getChildrenListMethod(tree)
  if (!childrenNodeList || childrenNodeList.length === 0) {
    return true
  }
  for (const node of childrenNodeList) {
    if (before && !before(node, level, tree)) {
      return false
    }
    if (!treeForeachDFS(node, before, after, getChildrenListMethod, level + 1)) {
      return false
    }
    if (after && !after(node, level, tree)) {
      return false
    }
  }
  return true
}

/**
 * 在森林中删除指定节点（排除节点），其子节点也会被删除
 *
 * 在forest原有基础上原地修改
 *
 * @param forest 森林
 * @param excludeNodeId 要排除的节点id列表
 * @param getIdMethod 获取id的方式
 * @param getChildrenListMethod 获取子节点列表的方式
 * @author 郭泳辰
 */
function excludeNodeDFS<NODE, S>(
  forest: NODE[] | undefined,
  excludeNodeId: S[],
  getIdMethod: (node: NODE) => S,
  getChildrenListMethod: (node: NODE) => NODE[] | undefined
): void {
  if (!forest || forest.length === 0) return
  for (let i: number = 0; i < forest.length; i++) {
    if (excludeNodeId.includes(getIdMethod(forest[i]))) {
      // 删除节点（终止条件）
      forest.splice(i, 1)
      i--
    } else {
      // 继续递归
      excludeNodeDFS(getChildrenListMethod(forest[i]), excludeNodeId, getIdMethod, getChildrenListMethod)
    }
  }
}

/**
 * 树工具
 */
export const TreeUtil = {
  /**
   * 递归遍历树形数据，查找到目标节点的路径
   *
   * @param id 寻找的节点id
   * @param forest 森林
   * @param getIdMethod 获取id的方法
   * @param getChildrenListMethod 获取子级列表的方法
   */
  findPathFromForest<S, T>(
    id: S,
    forest: T[] | undefined,
    getIdMethod: (node: T) => S,
    getChildrenListMethod: (node: T) => T[] | undefined
  ): T[] {
    const result: T[] = []
    findPathFromForestDFS(id, forest, result, getIdMethod, getChildrenListMethod)
    return result
  },

  /**
   * 森林通用深度优先遍历工具
   * @param forest 森林

   * @param before 在递归之前调用，类似前序遍历。
   *    - node：为当前节点
   *    - level：为当前节点的层级（从1开始）
   *    - parentNode：为当前节点的上级节点（如果没有上级节点则为undefined）
   *    - 返回值：返回true表示继续递归，返回false表示立即停止整个递归
   *
   * @param after 在递归之后调用，类似后序遍历。
   *    - node：为当前节点
   *    - level：为当前节点的层级（从1开始）
   *    - parentNode：为当前节点的上级节点（如果没有上级节点则为undefined）
   *    - 返回值：返回true表示继续递归，返回false表示立即停止整个递归
   *
   * @param getChildrenListMethod 获取子节点列表的方式，默认使用children字段
   * @param level 递归层级，默认从1开始，默认1
   * @return boolean
   *         对于递归过程来说：true继续递归，false停止整个递归
   *         对于调用者来说：true表示完成递归所有节点，false表示在before或after参数控制下递归提前终止
   * @author 郭泳辰
   */
  foreachDFS<NODE>(
    forest: NODE[] | undefined,
    before?: (node: NODE, level: number, parentNode?: NODE) => boolean,
    after?: (node: NODE, level: number, parentNode?: NODE) => boolean,
    getChildrenListMethod: (node: NODE) => NODE[] | undefined = getChildrenListMethodDefault,
    level: number = 1
  ): boolean {
    if (!forest || forest.length === 0) {
      return true
    }
    for (const node of forest) {
      if (before && !before(node, level, undefined)) {
        return false
      }
      if (!treeForeachDFS<NODE>(node, before, after, getChildrenListMethod, level + 1)) {
        return false
      }
      if (after && !after(node, level, undefined)) {
        return true
      }
    }
    return true
  },

  /**
   * 森林转为有向图
   *
   * @param forest 森林
   * @param getIdMethod 获取id的方式
   * @param getChildrenListMethod 获取子节点列表的方式
   * @param setLevelMethod 设置节点层级的方式（层级从1开始）
   * @return DirectedGraph<S, NODE> 有向图
   * @author 郭泳辰
   */
  forestToDirectedGraph<S, NODE>(
    forest: NODE[] | undefined,
    getIdMethod: (node: NODE) => S,
    getChildrenListMethod: (node: NODE) => NODE[] | undefined,
    setLevelMethod?: (node: NODE, level: number) => number
  ): DirectedGraph<S, NODE> {
    const graph: DirectedGraph<S, NODE> = new DirectedGraph<S, NODE>()
    TreeUtil.foreachDFS(
      forest,
      (node: NODE, level: number, parentNode?: NODE): boolean => {
        setLevelMethod?.(node, level)
        graph.nodeList.push(node)
        if (parentNode) {
          graph.edgeList.push({ from: getIdMethod(parentNode), to: getIdMethod(node) })
        }
        return true
      },
      undefined,
      getChildrenListMethod
    )
    return graph
  },

  /**
   * 查找指定节点
   */
  findTree<NODE>(
    forest: NODE[],
    getChildrenListMethod: (node: NODE) => NODE[] | undefined,
    condition: (node: NODE) => boolean
  ): NODE | undefined {
    let resultNode: NODE | undefined = undefined
    TreeUtil.foreachDFS(
      forest,
      (node: NODE): boolean => {
        if (condition(node)) {
          resultNode = node
          return false
        }
        return true
      },
      undefined,
      getChildrenListMethod
    )
    return resultNode
  },

  /**
   * 在森林中删除指定节点（排除节点），其子节点也会被删除
   *
   * 在forest原有基础上原地修改
   *
   * @param forest 森林
   * @param excludeNodeId 要排除的节点id列表
   * @param getIdMethod 获取id的方式，默认字段为id
   * @param getChildrenListMethod 获取子节点列表的方式，默认字段为children
   * @author 郭泳辰
   */
  excludeNode<NODE, S>(
    forest: NODE[],
    excludeNodeId: S[],
    getIdMethod: (node: NODE) => S = getIdMethodDefault,
    getChildrenListMethod: (node: NODE) => NODE[] | undefined = getChildrenListMethodDefault
  ): void {
    if (!forest || forest.length === 0 || !excludeNodeId || excludeNodeId.length === 0) return
    excludeNodeDFS(forest, excludeNodeId, getIdMethod, getChildrenListMethod)
  },

  /**
   * 将森林转为列表，以返回值形式返回列表
   * @param forest 森林
   * @param getChildrenListMethod 获取子节点列表的方式，默认字段为children
   * @param type 遍历方式，默认为先序遍历
   * @return NODE[] 转换后的列表（其子节点依然被保留），如果 forest 为空，则返回空数组
   */
  toList<NODE>(
    forest: NODE[],
    getChildrenListMethod: (node: NODE) => NODE[] | undefined = getChildrenListMethodDefault,
    type: '先序' | '后序' = '先序'
  ): NODE[] {
    const result: NODE[] = []
    if (!forest || forest.length === 0) {
      return result
    }
    if (type === '先序') {
      TreeUtil.foreachDFS(
        forest,
        (node: NODE): boolean => {
          result.push(node)
          return true
        },
        undefined,
        getChildrenListMethod
      )
    } else if (type === '后序') {
      TreeUtil.foreachDFS(
        forest,
        undefined,
        (node: NODE): boolean => {
          result.push(node)
          return true
        },
        getChildrenListMethod
      )
    } else {
      throw new Error(`不支持的转换方式：${type}`)
    }
    return result
  },
}

/**
 * ## 默认获取id的方法
 * @param node
 */
export const getIdMethodDefault = (node: any) => node.id

/**
 * ## 默认获取子节点列表的方法
 * @param node
 */
export const getChildrenListMethodDefault = (node: any) => node.children

/**
 * ## 有向图数据结构对象
 *
 * `<S, NODE>`分别表示节点的id类型与节点类型
 *
 * - `nodeList`表示点集合
 * - `edgeList`表示边集合，其中箭头方向是由from指向to
 */
class DirectedGraph<S, NODE> {
  nodeList: NODE[] = []
  edgeList: { from: S; to: S }[] = []
}
